Today, more and more people carry portable electronic devices including laptop computers, hand-held phones, Personal Digital Assistants (PDAs), and Moving Picture Experts Group Audio-Layer 3 (MP3) players. Most of these devices operate independently. If portable electronic devices form a wireless network in a self-configurable fashion without the aid of a central control system, they can easily share a variety of pieces of information and thus provide new diverse information communication services to their users. Such a wireless network that enables communications between portable electronic devices without assistance of the central control system anywhere at any time is called an ad hoc network or a ubiquitous network. The ad hoc network was developed first for military purposes in the 1970's and then found its applications in battlefields or emergency/disaster situations.
Providing services with diverse Quality of Service (QoS) requirements to users at high data rates is an active study area for a future-generation communication system called 4th Generation (4G). To enable high-speed communications and to accommodate an increasing number of calls, the 4G communication system requires cells with very small radiuses. In this context, a multi-hop relay network has attracted much interest in that it can expand cell coverage and increase system capacity by use of a multi-hop relay scheme. The cellular network establishes a multi-hop relay path between a base station (BS) and a mobile station (MS) via relay stations, if the channel status between the BS and the MS is poor, thereby providing a better channel to the MS. Consequently, the use of multi-hop relaying provides communication services more efficiently in a shadowing area experiencing severe shielding effects due to buildings or other obstacles. Also, a high-speed data channel can be provided at a cell boundary where mobile stations are placed in poor channel status, thus expanding cell coverage.
FIG. 1 illustrates the configuration of a multi-hop cellular system. Referring to FIG. 1, the multi-hop cellular system includes a BS 100, relay stations 110 and 120 managed by the BS 100, and mobile stations 112, 114, 122, 124 and 126.
Because the single BS 100 manages and communicates with the plurality of relay stations 110 and 120, when it transmits data to one RS, for example, the RS 110, the data transmission interferes with the neighbor RS 120. That is, wireless relay stations interfere with one another during transmission and reception in the multi-hop cellular system. A major technique for minimizing the interference and increasing throughput is centralized scheduling.
In the centralized scheduling scheme, the products of a capacity and a queue length is computed for every simultaneous transmission link set and a simultaneous transmission link set having the highest product is selected. In other words, a link set with the largest capacity and the longest queue is chosen by searching all possible simultaneous transmission link sets. For more details of the centralized scheduling scheme, see Viswanathan, H. and Mukherjee, S., “Performance of Cellular Networks with Relays and Centralized Scheduling”, Wireless Communications, IEEE Transactions on September 2005.
A shortcoming with the centralized scheduling scheme is, however, that complexity increases exponentially with the number of mobile stations or relay stations and the need for the queue lengths of the relay stations in the BS requires additional signaling. Moreover, it is impossible for the BS to acquire the Signal-to-Interference and Noise Ratio (SINR) of each link required for capacity computation and the BS should notify relay stations included in a selected simultaneous transmission link set that they are selected for data transmission, causing a time delay.